#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;
/*
    2022 4-17 网易互娱面试题
    

*/
namespace netease{
namespace April_17_2022{
class solve_net_ease2_zkm {
/*
    输入：
    2 - 2个测试用例
    12 - 12个人 （每个人分属于1-6号房间）
    1 12 6 
    1号房间中的某一个人 有12的概率 发出6的攻击力

    求：
    6个房间中每个房间取一个人，要求概率和>=100，且攻击力最高，若不存在输出“TAT”
    2
    12
    1 12 6
    1 14 10
    2 22 3
    2 3 38
    3 24 1
    3 3 15
    3 11 23
    4 13 2
    5 19 10
    5 17 11
    5 16 2
    6 20 2
    1
    11
    1 14 16
    1 17 3
    2 6 32
    3 3 24
    4 12 3
    4 13 0
    5 22 5
    5 21 4
    6 3 37
    6 14 6
    6 23 0
*/

public:
    solve_net_ease2_zkm() {
        auto data = get_data();
        cout << higheset(data) << endl;
        data = get_data2();
        cout << higheset(data) << endl;
    }

    void dfs(int index, vector<vector<pair<int, int>>>& arr, int cur_attack, int cur_prob, int& ans) {
        if (index == 6) {
            if (cur_prob >= 100) {
                ans = max(ans, cur_attack);
            }
            return;
        }
        dfs(index + 1, arr, cur_attack + arr[index][0].first, cur_prob + arr[index][0].second, ans);

        for (int i = 1; i < arr[index].size(); i++) {
            if (cur_prob + arr[index][i - 1].second >= 100) {
                return;
            }
            dfs(index + 1, arr, cur_attack + arr[index][i].first, cur_prob + arr[index][i].second, ans);
        }
    }

    int higheset(vector<vector<pair<int, int>>>& arr) {
        // arr 6 x {attack , prob}
        for (int i = 0; i < 6; ++i) {
            sort(arr[i].begin(), arr[i].end(), [](const pair<int, int>& a, const pair<int, int>& b) {
                return a.first == b.first ? a.second > b.second:a.first > b.first;
                });
        }
        vector<vector<pair<int, int>>> ans;
        for (int i = 0; i < 6; ++i) {
            queue<pair<int, int>> q;
            q.push(arr[i][0]);
            for (int j = 1; j < arr[i].size(); ++j) {
                if (q.back().second < arr[i][j].second) {
                    q.push(arr[i][j]);
                }
            }
            vector<pair<int, int>> one;
            while (!q.empty()) {
                one.push_back(q.front());
                q.pop();
            }
            ans.push_back(one);
        }
        int prob = 0;
        int attack = 0;
        for (int i = 0; i < 6; ++i) {
            prob += ans[i][0].second;
            attack += ans[i][0].first;
        }
        if (prob >= 100)return attack;
        int res = 0;
        dfs(0, ans, 0, 0, res);
        return res;
    }
    vector<vector<pair<int, int>>> get_data() {
        vector<vector<pair<int, int>>> ans;
        ans = {
            {{ 12 ,6},{14, 10}},
            {{ 22, 3},{3 ,38}},
            {{ 24, 41},{3 ,15},{11, 23}},
            {{ 13 ,2}},
            {{ 19, 10},{17, 11},{16, 2}},
            {{ 20, 2}}
        };
        return ans;
    }

    vector<vector<pair<int, int>>> get_data2() {
        vector<vector<pair<int, int>>> ans;
        ans = {
            { {14 ,16},
              {17 ,3 }},
            { {6  ,32}},
            { {3  ,24}},
            { {12 ,3 },
              {13 ,0 }},
            { {22 ,5 },
              {21 ,4 }},
            { {3  ,37},
             {14 ,6 },
             {23 ,0 }}
        };
        return ans;
    }

};

}
}